package com.berchen.算法.排序;

import java.time.Duration;
import java.time.Instant;
import java.util.Arrays;

/**
 * 希尔排序  插入排序升级版本
 */
public class ShellSort {

    public static void main(String[] args) {
        int size = 80000;
        int[] testArr = new int[size];
        for (int i = 0; i < size; i++) {
            testArr[i] = (int) (Math.random() * size);
        }

        Instant start=Instant.now();
        shellSort(testArr);
        Instant end=Instant.now();
        System.out.println(Duration.between(start,end).toMillis()); // 34
//        System.out.println(Arrays.toString(testArr));
    }

    /**
     * 希尔排序
     * @param arr
     */
    public static void shellSort(int[] arr ){

        // 循环步长
        for(int tab=arr.length/2;tab>=1;tab/=2){
            // 每个步长里面进行插入排序
            for(int i =tab;i<arr.length;i++){
                int insertValue=arr[i];
                int insertIndex=i-tab;
                while(insertIndex>=0&&arr[insertIndex]>insertValue){
                    arr[insertIndex+tab]=arr[insertIndex];
                    insertIndex-=tab;
                }
                arr[insertIndex+tab]=insertValue;
            }
        }
    }
}
